package 优先级队列;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/find-k-pairs-with-smallest-sums/
 */
public class _373_查找和最小的K对数字 {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>> lists = new ArrayList<>();
        PriorityQueue<List<Integer>> queue = new PriorityQueue<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return o1.get(0) - o2.get(0);
            }
        });
        for (int i = 0; i < nums1.length; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(nums1[i]);
            if (i < nums2.length) {
                list.add(nums2[i]);
            } else {
                list.add(nums2[nums2.length - 1]);
            }
            Collections.sort(list, new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            });
            queue.add(list);

        }
        int i = 0;
        while (i < k){
            lists.add(queue.remove());
            i++;
        }
        return lists;
    }
}
